//
// Created by yanhai on 2021/1/3.
//

// 冒泡排序

#include <stdio.h>

#define ARRAY_DATA_LENGTH 16

void print(int *data, int length)
{
    for (int i = 0; i < length; i++) {
        printf("%d ", data[i]);
    }
    printf("\n");
}

void swap(int *a, int *b)
{
    int tmp = *a;
    *a = *b;
    *b = tmp;
}

// 第一种冒泡排序
// i指向第一个元素，然后j为i后面的元素，依次比较，前面的大就交换位置，第一轮结束后，第1个位置的元素就是最小的。
// i向后移动一个位置，然后与后面的所有位置j元素进行比较，结束后，第2个位置的元素就是第2小的元素
// 依次进行，直到i到达倒数第二个位置，就将所有的元素比较一遍了。此时数组就是有序的。
// 每一次遍历，就是把剩下的当中的最小值放到最前面，最小值就是这样像冒泡的方式一点一点移动到最前面的。
void bubble_sort1(int *data, int length)
{
    int i = 0, j = 0;
    for (i = 0; i < length - 1; i++) {
        for (j = i + 1; j < length; j++) {
            if (data[i] > data[j]) {
                swap(&data[i], &data[j]);
            }
        }
    }
}

// 第二种冒泡排序，正宗的冒泡排序(比较相邻的两个元素)
// n个元素，先比较第n-1和n元素，再比较 n-2和n-1，直到 比较第1个和第2个元素，至此，第1个元素就是最小的了
// 然后再按同样的方式，排序后面的n-1个元素
void bubble_sort2(int *data, int length)
{
    int i = 0, j = 0;
    for (i = 0; i < length - 1; i++) {
        for (j = length - 1; j > i; j--) {
            if (data[j - 1] > data[j]) {
                swap(&data[j - 1], &data[j]);
            }
        }
    }
}

// 第三种冒泡排序 -- 改进第二种方式
// 假如后面n-m个元素已经是顺序的了，但是按照第2种方式，依然还是要对后面的n-m所有的元素进行遍历比较，
// 时间复杂度： 1. 如果已经是一个排序好的数组，则仅需要比较n-1次
//            2. 如果是一个逆序的数组，则需要比较 n-1+n-2+...+3+2+1=n(n-1)/2次，
//            因此，总的时间复杂度为O(n^2)
void bubble_sort3(int *data, int length)
{
    int i = 0, j = 0;
    int need_sort = 1;
    for (i = 0; i < length - 1 && need_sort; i++) { // 如果不需要排序，则退出循环
        need_sort = 0; // 默认置为0
        for (j = length - 1; j > i; j--) {
            if (data[j - 1] > data[j]) {
                swap(&data[j - 1], &data[j]);
                need_sort = 1; // 如果有数据交换，则还需要排序
            }
        }
    }
}

int main()
{
    int data[ARRAY_DATA_LENGTH] = {23, 64, 24, 12, 9, 16, 53, 57, 71, 79, 87, 97, 45, 60, 61, 90};

    print(data, ARRAY_DATA_LENGTH);
    bubble_sort3(data, ARRAY_DATA_LENGTH);
    print(data, ARRAY_DATA_LENGTH);

    return 0;
}
